/*
Anagrams
Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

*/
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
		vector<string> result;
		map<string,int> dic;
		
		map<string,int>::iterator it;
		
		for(int i = 0; i < strs.size();i++)
		{
			string temps = strs[i];
			sort(temps.begin(),temps.end());
			
			it = dic.find(temps);
			
			if(it == dic.end())
			{
				dic[temps] = i;
			}
			else
			{
				if(dic[temps] == -1)
				{
					result.push_back(strs[i]);
				}	
				else{
					result.push_back(strs[dic[temps]]);
					dic[temps] = -1;
					result.push_back(strs[i]);
				}
			}
			
		}
		
		
		return result; 
    }
};

int main(int argc, char* argv[])
{
	cout<<"Anagrams"<<endl;
	vector<string> strs, result;
	strs.push_back("ate");
	strs.push_back("tea");
	strs.push_back("bat");
	
	cout<<"Input strings"<<endl;
	
	for(int i = 0; i<strs.size();i++)
	{
		cout<<strs[i]<<" ";
	}
	cout<<endl;
	
	Solution s;
	result = s.anagrams(strs);
	
	
	for(int i = 0; i<result.size();i++)
	{
		cout<<result[i]<<" ";
	}
	cout<<endl;
	
	return 0;
}